BZOJ2753【SCOI2012】滑雪与时间胶囊 < MST >

Problem

【SCOI2012】滑雪与时间胶囊

Description

非常喜欢滑雪。他来到一座雪山，这里分布着条供滑行的轨道和个轨道之间的交点（同时也是景点），而且每个景点都有一编号（）和一高度。能从景点滑到景点当且仅当存在一条和之间的边，且的高度不小于。与其他滑雪爱好者不同，喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。于是拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上个经过的景点（不用移动也不被认为是滑行的距离）。请注意，这种神奇的药物是可以连续食用的，即能够回到较长时间之前到过的景点（比如上上个经过的景点和上上上个经过的景点）。现在，站在号景点望着山下的目标，心潮澎湃。他十分想知道在不考虑时间胶囊消耗的情况下，以最短滑行距离滑到尽量多的景点的方案（即满足经过景点数最大的前提下使得滑行总距离最小）。你能帮他求出最短距离和景点数吗？

Input

输入的第一行是两个整数，。
接下来行有个整数，分别表示每个景点的高度。
接下来行，表示各个景点之间轨道分布的情况。每行个整数，。表示
编号为的景点和编号为的景点之间有一条长度为的轨道。

Output

输出一行，表示最多能到达多少个景点，以及此时最短的滑行距离总和。

Sample Input

Sample Output

3 2

HINT

对于的数据，保证
对于的数据，保证, , , 。

标签：MST

Solution

原题的一大坨叙述就是求有向图中从一点出发能达到的点数和最小生成树边权和。

第一问直接出解。
第二问比较麻烦，还是做，只是排序的时候以终点高度从高到低为第一关键字，以边权从低到高为第二关键字。

原理：
首先，同一高度的点间一定是双向边，于是是一个强连通分量，如果把每个高度的点缩起来，那么最后一定会形成一个，从开始沿拓扑序遍历每个强连通分量，这个强连通分量中的边都是双向边，可以在这个强连通分量中跑，除了这些边以外还可能有从上面的点连下来的点。因此如果按终点高度为第一关键字排序，那么到一个高度时一定是此高度强连通分量内部的双向边和前面连到此强连通分量的边，符合贪心的前提。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define MAX_M 2000000
#define pb push_back
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, p, h[MAX_N+5], fa[MAX_N+5];
vector <int> G[MAX_N+5]; bool mrk[MAX_N+5];
struct node {int u, v, w; lnt c;} E[MAX_M+5];
bool cmp (const node &a, const node &b) {
    return a.w == b.w ? a.c < b.c : a.w > b.w;
}
int getf(int x) {return fa[x] == x ? x : fa[x] = getf(fa[x]);}
int BFS() {
    int ret = 1;	mrk[1] = true;
    queue <int> que; que.push(1);
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = 0, v; i < (int)G[u].size(); i++)
            if (!mrk[v = G[u][i]]) que.push(v), mrk[v] = true, ret++;
    }
    return ret;
}
int main() {
    read(n), read(m);	lnt ans = 0;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= n; i++) read(h[i]);
    for (int i = 0; i < m; i++) {
        int u, v; lnt c; read(u), read(v), read(c);
        if (h[u] >= h[v]) G[u].pb(v), E[++p] = (node){u, v, h[v], c};
        if (h[u] <= h[v]) G[v].pb(u), E[++p] = (node){v, u, h[u], c};
    }
    sort(E+1, E+(m=p)+1, cmp), printf("%d ", BFS());
    for (int i = 1, u, v; i <= m; i++)
        if (mrk[E[i].u] && mrk[E[i].v]) {
            u = getf(E[i].u), v = getf(E[i].v);
            if (u^v) fa[u] = v, ans += E[i].c;
        }
    return printf("%lld\n", ans), 0;
}